#ifndef AI_SEARCH_H
#define AI_SEARCH_H



#include "ai.h"



/** @brief AI state, that is used to build a search tree
*
*   \image html ai_search.jpeg
*/
class ai_states_node
{

public:

	/**	@brief Constructor, that connects ai_game_state to states tree
	*	@param p parrent of the node
	*	@param s ai_game_state to be connected to the parent
	*/
	ai_states_node( ai_states_node* p, ai_game_state* s );

	//! @brief Destructor deletes all its children
	~ai_states_node();

	//! algorithm owner's score
	double my_score;
	//! current player's score
	double current_score;
	//! previous player's score
	double prev_score;

	//! parent of this node
	ai_states_node* parent;
	//! parent of this node at the end of previous level
	ai_states_node* level_parent;
	//! list of children
	list< ai_states_node* >* children;
	//! list of children at the beginning of next level
	list< ai_states_node* >* level_children;
	//! the ai_game_state
	ai_game_state* state;
	//! actual depth, where the node is
	int depth;
};



/** @brief The main algorithm class.
*
*	This algorithm is based on search of state space and generating state tree. The whole state space is being searched to depth set in
*	parameters::ai_parameters[ "SEARCH" ][ "depth" ]. Depth 1 means, that the state space will be searched to the end of first player's turn.
*	Depth 2 means, that it will be searched to the end of next player's turn and so on.*
*
*	At the beginning, the given game_state is used to create the root of whole tree composed of ai_states_node. For each ation, that can be done
*	on the node, the child is added. When the child contains "NXT" command, it is connected to ai_states_node::level_parent. Duplicities are
*	excluded using search_algorithm::searched_states_list.
*
*	At the end of search, we find the best commands. We assume, that every players is maximising his score and thinks one round to future,
*	so we search only states in search_algorithm::state_levels and when the enemy is on turn, we find for each child the one with maximum score
*	and we assume, that he will choose this state. The previous player is trying to avoid this player to maximise his score, so he will choose
*	the state, where his worst predictabe score is highest nad so on. When we get to root, we find the state with highest score for us and find
*	commands, how to get there.
*
*   \image html ai_search.jpeg
*/
class search_algorithm: public algorithm
{

public:

	//! @brief Constructor only assignes the name
	search_algorithm()
	{
		name = "Search algorithm";
		search_tree = 0;
		state_levels = 0;
		searched_states_list = 0;
	};

	//! @brief Destructor cleans all staff
	~search_algorithm()
	{
		if ( search_tree != 0 )
			delete search_tree;
		if ( state_levels != 0 )
			delete state_levels;
		if ( searched_states_list != 0 )
			delete searched_states_list;
	};

	/** @brief	Registrating function (adds ai algorithm to map)
	*/
	static void register_me()
	{
		register_metpl< search_algorithm >();
	};

	/** @brief	Cloning function for init purposes
	*	@return	clone of the algorithm
	*/
	virtual algorithm* clone()
	{
		search_algorithm* cl = clonetpl< search_algorithm >();
		return cl;
	};

	/** @brief Function called at the beginning of buy
	*	@param gs current game state
	*/
	virtual void get_buy_commands( const game_state* gs );
	/** @brief Function called at the beginning of every turn
	*	@param gs current game state
	*/
	virtual void get_commands( const game_state* gs );


private:

	/**	@brief Expands given state and connects all children
	*	@param state_node node to expand, constraint: state_node != 0
	*/
	void search_state( ai_states_node* state_node );

	//! pointer to the root of the tree
	ai_states_node* search_tree;

	/** @brief Adds state to list of searched states
	*	@param state game state to add, constraint: state != 0
	*/
	void add_to_list( game_state* state );
	/** @brief	Checks if the state was already searched
	*	@param	state game state to check, constraint: state != 0
	*	@return true if state is already in list and was searched, else false
	*/
	bool is_in_list ( game_state* state );

	//! map of searched states, indexed by hash, one field contains list of states with same hash
	map< unsigned long long int, list< game_state* > >* searched_states_list;

	//! vector of lists, where are all states in one depth, that are on the end of turn
	vector< list< ai_states_node* > >* state_levels;

	/** @brief	Finds form list of nodes the one with highest score for algorithm owner
	*	@param	node_list list where to find for the node
	*	@return	node with the highest score
	*/
	ai_states_node* find_max_score_me( list< ai_states_node* >* node_list );
	/** @brief	Finds form list of nodes the one with highest score for current player
	*	@param	node_list list where to find for the node
	*	@return	node with the highest score
	*/
	ai_states_node* find_max_score_curr( list< ai_states_node* >* node_list );
	/** @brief	Finds form list of nodes the one with highest score for previous player
	*	@param	node_list list where to find for the node
	*	@return	node with the highest score
	*/
	ai_states_node* find_max_score_prev( list< ai_states_node* >* node_list );

	//! remaining nodes to search
	unsigned int nodes_to_search;
	//! searched nodes
	unsigned int searched_nodes;

	//! given state - never changed
	const game_state* original_state;

};



#endif